package com.leetcode.algorithm.y22.m06;

/**
 * 264. 丑数 II
 * 
 * https://leetcode.cn/problems/ugly-number-ii/
 * 
 * @author jie.deng
 *
 */
class Question0264Solution01 {
	
	public int nthUglyNumber(int n) {
		int[] dp = new int[n];
		int[] idxArr = new int[3];
		int[] numArr = new int[3];

		// dp=[1]
		// 备选索引0,0,0
		// 备选数2*dp[0]=2,3*dp[0]=3,5*dp[0]=5
		dp[0] = 1;
		idxArr[0] = 0;
		idxArr[1] = 0;
		idxArr[2] = 0;
		numArr[0] = 2 * dp[idxArr[0]];
		numArr[1] = 3 * dp[idxArr[1]];
		numArr[2] = 5 * dp[idxArr[2]];

		// 第二轮
		// 取备选数2,3,5中较小者2
		// dp=[1,2]
		// 备选索引1,0,0
		// 备选数2*dp[1]=4,3*dp[0]=3,5*dp[0]=5

		// 第三轮
		// 取备选数4,3,5中较小者3
		// dp=[1,2,3]
		// 备选索引1,1,0
		// 备选数2*dp[1]=4,3*dp[1]=6,5*dp[0]=5

		for (int i = 1; i < n; i++) {
			int min = Math.min(numArr[0], numArr[1]);
			min = Math.min(min, numArr[2]);
			dp[i] = min;
			if (numArr[0] == min) {
				idxArr[0] += 1;
				numArr[0] = 2 * dp[idxArr[0]];
			}
			if (numArr[1] == min) {
				idxArr[1] += 1;
				numArr[1] = 3 * dp[idxArr[1]];
			}
			if (numArr[2] == min) {
				idxArr[2] += 1;
				numArr[2] = 5 * dp[idxArr[2]];
			}
		}

		return dp[n - 1];
	}
	
}